#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution01 {
public:
    bool canJump(vector<int>& nums) {
        int next = 0;
        int left = 0, right = 0;
        while (left <= right) {
            if (next >= nums.size() - 1) return true;

            for (int i = left; i <= right && i < nums.size(); i++) {
                next = max(nums[i] + i, next);
            }
            left = right + 1;
            right = next;
            // if (right >= nums.size() - 1) return true;
            // if (left > right) return false;
        }

        return false;
    }
};

class Solution02 {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // 可以先判断是否能走通
        int n = cost.size(), sum = 0;
        vector<int> diff(n);
        for (int i = 0; i < n; i++)
            diff[i] = gas[i] - cost[i], sum += diff[i];
        if (sum < 0) return -1;
        
        for (int i = 0; i < n; i++) {
            int pos = i;
            if (diff[i] < 0) continue;

            int cnt = diff[pos];
            pos = (pos + 1) % n;

            // int next = 0;

            while (pos != i) {
                cnt += diff[pos];
                pos = (pos + 1) % n;
                if (cnt < 0) {
                    // i = (pos) % n;
                    break;
                }
            }
            if (pos == i && cnt >= 0) return i;
            i = pos - 1;
        }

        return -1;
    }
};

class Solution03 {
    bool isInrease(int num) {
        string s = to_string(num);
        for (int i = 0; i < s.size() - 1; i++)
            if (s[i] > s[i + 1]) return false;
        return true;
    }
public:
    int monotoneIncreasingDigits(int n) {
        if (n < 10) return n;
        // for (int i = n; i >= 0; i--) {
        //     if (isInrease(i)) return i;
        // }
        // return 0;
        // 可以先拿到最高位，若最高位大于次第位，直接返回
        string num = to_string(n);
        int i = 0, len = num.size();
        while (i < len - 1) {
            if (num[i] > num[i + 1])
                break;
            i++;
        }
        if (i == len - 1) return stoi(num);
        // 向前扫描
        while (i > 0) {
            if (num[i] == num[i - 1]) i--;
            else break;
        }
        num[i] = num[i] - 1;
        // 然后将后面的数全改为9
        for (int j = i + 1; j < len; j++) {
            num[j] = '9';
        }

        return stoi(num);
    }
};

class Solution04 {
public:
    int brokenCalc(int startValue, int target) {
        // 先判断target是奇数还是偶数
        // if (target <= startValue) return startValue - target;
        // 正难则反
        int end = target, begin = startValue;
        int sum = 0;
        while (end != begin) {
            if (end <= begin) {
                sum += begin - end;
                break;
            } else {
                if (end % 2 == 1) 
                    end = end + 1;
                else 
                    end /= 2;
            }
            sum++;
        }

        return sum;
    }
};

class Solution05 {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // // if (intervals.size() == 1)
        // //     return intervals;
        // vector<vector<int>> ret;
        // int n = intervals.size();

        // sort(intervals.begin(), intervals.end(),
        //      [&](const vector<int>& i, const vector<int>& j) {
        //          return i[0] < j[0];
        //      });

        // // for (int i = 0; i < n - 1; i++) {
        // //     vector<int> front = intervals[i], back = intervals[i + 1];
        // //     // 使用函数
        // // }
        // int left = 0, right = 1;
        // while (right < n) {
        //     //
        //     int prev = intervals[left][1];
        //     while (right < n && intervals[right][0] <= prev) {
        //         prev = max(intervals[right][1], prev);
        //         right++;
        //     }
        //     // 走在这里 intervals[right][0] < prev 说明这个位置不可以合并
        //     if (prev > intervals[left][1])
        //         ret.push_back({intervals[left][0], prev});
        //     else
        //         ret.push_back(intervals[left]);
        //     left = right;
        //     right++;
        // }
        // if (left < n) {
        //     ret.push_back(intervals[left]);
        // }
        // // 最后一个区间还没有放上去
        // // if (ret.back()[1] != intervals.back()[1])
        // // ret.push_back(intervals.back());
        // return ret;
        vector<vector<int>> ret;
        sort(intervals.begin(), intervals.end(),
             [&](const vector<int>& i, const vector<int>& j) {
                 return i[0] < j[0];
        });        

        int left = intervals[0][0], right = intervals[0][1];

        for (int i = 1; i < intervals.size(); i++) {
            int a = intervals[i][0], b = intervals[i][1];
            if (a <= right) {
                right = max(right, b);
            } else {
                ret.push_back({left, right});
                left = a, right = b;
            }
        }
        ret.push_back({left, right});
        return ret;
    }
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int len = intervals.size();
        sort(intervals.begin(), intervals.end());
        int right = intervals[0][1];
        
        int index = 0;
        int ret = 0;
        for (int i = 1; i < intervals.size(); i++) {
            int b = intervals[i][1], a = intervals[i][0];
            if (right > a) {
                // 删除元素
                // if (b >= right) intervals.erase(intervals.begin() + i);
                // else intervals.erase(intervals.begin() + index), right = b, index = i;
                right = min(right, b);
                ret++;
                // i++;
            } else {
                right = b;
                // index = i;
                // i++;
            }
        }
        return ret;
    }
};

int main() {

    return 0;
}